package leetcode.editor.cn.q1_300.q50;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author qidi
 * @date 2021-12-28 09:31:04
 */
class Q0093_RestoreIpAddresses {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private List<String> result = new ArrayList<>();
        private LinkedList<String> cur = new LinkedList<>();

        public List<String> restoreIpAddresses(String s) {
            if (s.length() < 4 || s.length() > 12) return result;

            process(s, 0, 0);

            return result;
        }

        /**
         * @param m 第 m 个数
         * @param n 当前的下标为 n
         */
        private void process(String s, int m, int n) {
            if (4 - m > s.length() - n || (4 - m) * 3 < s.length() - n) return;
            if (m == 4 && n == s.length()) {
                result.add(cur.stream().collect(Collectors.joining(".")));
                return;
            }

            for (int i = 1; i <= 3; i++) {
                if (n + i > s.length()) break;
                String sub = s.substring(n, n + i);
                if (i == 1 || s.charAt(n) != '0' && Integer.parseInt(sub) <= 255) {
                    cur.add(sub);
                    process(s, m + 1, n + i);
                    cur.removeLast();
                }
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0093_RestoreIpAddresses().new Solution();
        System.out.println(solution.restoreIpAddresses("25525511135"));
        System.out.println(solution.restoreIpAddresses("0000"));
        System.out.println(solution.restoreIpAddresses("1111"));
        System.out.println(solution.restoreIpAddresses("010010"));
        System.out.println(solution.restoreIpAddresses("101023"));
    }
}